import java.util.*;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 23735
 * Date: 2023-05-14
 * Time: 10:33
 */

class Trie{
    // Character 代表这一层的字母
    // Trie 代表下一层
    Map<Character, Trie> children;
    public Trie(){
        this.children = new HashMap<>();
    }
}


public class Solution {
    public static String replaceWords(List<String> dictionary, String sentence) {
        // 构造前缀树
        Trie trie = new Trie();
        for (String root: dictionary) {
            // 注意这个是每重新放入一个单词是都要从头开始
            Trie cur = trie;
            for (Character c: root.toCharArray()) {
                // 没有这个字母时再放
                if (!cur.children.containsKey(c)){
                    cur.children.put(c, new Trie());
                }
                // 下一层, 每个单词前缀对应多层, 每层放这个单词的一个字母
                cur = cur.children.get(c);
            }
            // 最后以 '#' 结尾
            cur.children.put('#', null);
        }
        // 根据前缀树进行查找替换
        String[] words = sentence.split(" ");
        for (int i = 0; i < words.length; i++) {
            words[i] = findRoot(trie , words[i]);
        }
        return String.join(" ", words);
    }

    private static String findRoot(Trie trie, String word) {
        Trie cur = trie;
        StringBuilder res = new StringBuilder();
        for (Character c: word.toCharArray()) {
            // 因为是找最短的, 所以只要这一层有结束的, 那么这个结束的就是最短的
            if (cur.children.containsKey('#')){
                return res.toString();
            }
            // 没有找到前缀
            if (!cur.children.containsKey(c)){
                return word;
            }
            res.append(c);
            cur = cur.children.get(c);
        }
        return res.toString();
    }
}
